public class Test38 {
    public int minCut(String s) {
        int n = s.length();
        boolean f[][] = new boolean[n][n];
        int dp[] = new int[n];
        for(int i = 0;i < n;i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        for(int i = n - 1;i >= 0;i--) {
            for(int j = i;j < n;j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    f[i][j] = j - i < 2 ? true : f[i + 1][j - 1];
                }
            }
        }

        for(int i = 0;i < n;i++) {
            if(f[0][i]){
                dp[i] = 0;
            } else {
                for(int j = i;j > 0;j--) {
                    if(f[j][i]) {
                        dp[i] = Math.min(dp[i],dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[n - 1];
    }
}
